In communications networks, there may be a challenge to obtain good performance and capacity for a given communications protocol, its parameters and the physical environment in which the communications network is deployed.
For example, one parameter in providing good performance and capacity for a given communications protocol in a communications network is the ability to provide different kinds of security mechanisms. One component used in different kinds of security mechanism is hash values. Hash values may be determined by using hash trees. In general terms, in cryptography and computer science, a hash tree or, specifically, a Merkle tree, is a tree in which every non-leaf node is labelled with the hash of the labels of its children nodes.
Hash trees are useful because they allow efficient and secure verification of the contents of large data structures. Hash trees are a generalization of hash lists and hash chains. Hash trees can be used to verify any kind of data stored, handled and transferred in and between computers.
In general terms, a Merkle tree is a binary hash tree of height n and having 2n leaves, where a node value is computed as the hash of the concatenation of its direct children values. Starting from leaf values one may compute the root hash value, also denoted root value or hash digest, associated with the root node of the tree.
Merkle trees have found many applications in various cryptographic schemes, such as hash-based one-time signatures, hash-based authentication schemes, and others. In those schemes, the hash path, also denoted verification path, from a leaf to the root contains n hashes and is seen as a proof of knowledge of the leaf value. In other schemes, the hash path, or verification path, is seen as the authentication of a one-time password or key, that is actually the leaf value.
The hash path in a Merkle tree is of size n times the size of the root value. For a large Merkle tree this may be a problem since the hash path becomes large, and the verification time needs to call a hash algorithm n times.
Hence, there is still a need for efficient verification paths for leaves in a tree and for efficient verification of such verification paths.